home *** CD-ROM | disk | FTP | other *** search
/ 17 Bit Software 6: Level 6 / 17 Bit - Level 6 (1998)(Epic Marketing)[!].iso / quartz / q0040.dms / q0040.adf / top / branch.c < prev    next >
C/C++ Source or Header  |  1990-12-06  |  11KB  |  482 lines
  1. /* Copyright (c) 1988 by Sozobon, Limited.  Author: Tony Andrews
  2.  *
  3.  * Permission is granted to anyone to use this software for any purpose
  4.  * on any computer system, and to redistribute it freely, with the
  5.  * following restrictions:
  6.  * 1) No charge may be made other than reasonable charges for reproduction.
  7.  * 2) Modified versions must be clearly marked as such.
  8.  * 3) The authors are not responsible for any harmful consequences
  9.  *    of using this software, even if they result from defects in it.
  10.  */
  11. #include "top.h"
  12.  
  13. static    int
  14. bcomp(bc)
  15. register int    bc;
  16. {
  17.     switch (bc) {
  18.     case BHI: return BLS;
  19.     case BLS: return BHI;
  20.     case BCC: return BCS;
  21.     case BCS: return BCC;
  22.     case BNE: return BEQ;
  23.     case BEQ: return BNE;
  24.     case BVC: return BVS;
  25.     case BVS: return BVC;
  26.     case BPL: return BMI;
  27.     case BMI: return BPL;
  28.     case BGE: return BLT;
  29.     case BLT: return BGE;
  30.     case BGT: return BLE;
  31.     case BLE: return BGT;
  32.     default:
  33.         fprintf(stderr, "bcomp() - bad branch code %d\n", bc);
  34.         exit(EXIT_FAILURE);
  35.     }
  36. }
  37.  
  38. /*
  39.  * isbranch(s) - determines if 's' is a branch opcode
  40.  *
  41.  * Returns 1 for branches whose destination is the first operand,
  42.  * and 2 for branches whose dest. is the second.
  43.  */
  44. static    int
  45. isbranch(c)
  46. register int    c;
  47. {
  48.     switch (c) {
  49.     case BRA: case BHI: case BLS: case BCC:
  50.     case BCS: case BNE: case BEQ: case BVC:
  51.     case BVS: case BPL: case BMI: case BGE:
  52.     case BLT: case BGT: case BLE:
  53.         return 1;
  54.  
  55.     case DBRA: case DBHI: case DBLS: case DBCC:
  56.     case DBCS: case DBNE: case DBEQ: case DBMI:
  57.     case DBGE: case DBLT: case DBGT: case DBLE:
  58.     case  DBT:
  59.         return 2;
  60.  
  61.     default:
  62.         return 0;
  63.     }
  64. }
  65.  
  66. /*
  67.  * cblock(cp) - return the first block containing some code
  68.  *
  69.  * Starting with 'cp', find a block that has one or more instructions
  70.  * in it. This is useful to collapse multiple null blocks into a single
  71.  * logical point.
  72.  */
  73. static    BLOCK *
  74. cblock(bp)
  75. register BLOCK    *bp;
  76. {
  77.     while (bp->first == NULL && bp->bcond == NULL) {
  78.         if (bp->bfall == NULL) {
  79.             fprintf(ofp, "cblock() - error in block %s\n",
  80.                 bp->name);
  81.             exit(EXIT_FAILURE);
  82.         }
  83.         bp = bp->bfall;
  84.     }
  85.  
  86.     return bp;
  87. }
  88.  
  89. /*
  90.  * bsplit() - split up blocks with branches inside them
  91.  *
  92.  * Look for branch instructions in each block. If somewhere in the middle of
  93.  * the block, split up the block. When done, the blocks are broken down into
  94.  * true basic blocks.
  95.  */
  96. static    void
  97. bsplit(bp)
  98. BLOCK    *bp;
  99. {
  100.     register BLOCK    *cp;    /* the current block */
  101.     register BLOCK    *np;    /* new block (if needed) */
  102.     register INST    *ip;    /* current instruction */
  103.  
  104.     for (cp = bp; cp != NULL ;cp = cp->chain) {
  105.         for (ip = cp->first; ip != NULL ;ip = ip->next) {
  106.             if (isbranch(ip->opcode) && ip->next != NULL) {
  107.                 np = mksym(mktmp());
  108.  
  109.                 np->chain = cp->chain;
  110.                 cp->chain = np;
  111.  
  112.                 np->next = cp->next;
  113.                 cp->next = np;
  114.  
  115.                 np->first = ip->next;
  116.                 np->first->prev = NULL;
  117.                 np->last = cp->last;
  118.  
  119.                 cp->last = ip;
  120.                 cp->last->next = NULL;
  121.  
  122.             } else if (ip->opcode == DC) {
  123.                 BLOCK    *db;
  124.  
  125.                 /*
  126.                  * If the instruction is part of a branch
  127.                  * table, both the current block and the
  128.                  * destination need to be marked as "reached".
  129.                  */
  130.                 cp->flags |= B_ISREACHED;
  131.  
  132.                 if ((db = getsym(ip->src.astr)) != NULL)
  133.                     db->flags |= B_ISREACHED;
  134.                 else {
  135.                     fprintf(stderr, "bsplit() - symbol '%s' not found\n", ip->src.astr);
  136.                     exit(EXIT_FAILURE);
  137.                 }
  138.             }
  139.         }
  140.     }
  141. }
  142.  
  143. /*
  144.  * bfix() - fix up the branch pointers
  145.  *
  146.  * Go through each block setting up 'bcond' and 'bfall' properly. If the
  147.  * last instruction in the block is an unconditional branch, remove it
  148.  * and set 'bfall' instead.
  149.  */
  150. static    void
  151. bfix(bp)
  152. register BLOCK    *bp;
  153. {
  154.     register BLOCK    *cp;    /* current block */
  155.     register INST    *ip;    /* current instruction */
  156.  
  157.     for (cp = bp; cp != NULL ;cp = cp->chain) {
  158.  
  159.         /* no instructions in the block */
  160.         if (cp->first == NULL) {
  161.             cp->bcond = NULL;
  162.             cp->bfall = cp->next;
  163.             continue;
  164.         }
  165.  
  166.         /* the last instruction is a "return" */
  167.         if (cp->last->opcode == RTS) {
  168.             cp->bcond = cp->bfall = NULL;
  169.             cp->flags |= B_RET;
  170.             continue;
  171.         }
  172.  
  173.         /* the last instruction isn't a branch */
  174.         if (!isbranch(cp->last->opcode)) {
  175.             cp->bcond = NULL;
  176.             cp->bfall = cp->next;
  177.             continue;
  178.         }
  179.  
  180.         /*
  181.          * If we reach this point, then we've got a branch we need
  182.          * to remove at the end of this block.
  183.          */
  184.         cp->bfall = cp->next;
  185.         if (isbranch(cp->last->opcode) == 1) {
  186.             cp->bcode = cp->last->opcode;
  187.             cp->bcond = getsym(cp->last->src.astr);
  188.         } else {
  189.             cp->bcode = -1;
  190.             cp->bcond = getsym(cp->last->dst.astr);
  191.         }
  192.  
  193.         if (cp->bcond == NULL) {
  194.             fprintf(stderr, "top: branch to bad label '%s'\n",
  195.                 cp->last->src.astr);
  196.             exit(EXIT_FAILURE);
  197.         }
  198.  
  199.         if (cp->bcode < 0)
  200.             continue;
  201.  
  202.         for (ip = cp->first; ip != NULL ;ip = ip->next) {
  203.             if (ip->next == cp->last) {
  204.                 ip->next = NULL;
  205.                 break;
  206.             }
  207.         }
  208.         free(cp->last->src.astr);
  209.         free(cp->last);
  210.  
  211.         if (cp->first == cp->last)
  212.             cp->first = cp->last = NULL;
  213.         else
  214.             cp->last = ip;
  215.         /*
  216.          * If the branch was unconditional, we want to represent
  217.          * it as a "fall through", so fix the pointers to do that.
  218.          */
  219.         if (cp->bcode == BRA) {
  220.             s_bdel++;
  221.             cp->bfall = cp->bcond;
  222.             cp->bcond = NULL;
  223.         }
  224.     }
  225. }
  226.  
  227. /*
  228.  * bclean() - remove references to empty blocks
  229.  *
  230.  * Called after bsplit() and bfix().
  231.  */
  232. static    void
  233. bclean(bp)
  234. register BLOCK    *bp;
  235. {
  236.     register BLOCK    *cp;
  237.  
  238.     /*
  239.      * First clean up references to empty blocks
  240.      */
  241.     for (cp = bp; cp != NULL ;cp = cp->chain) {
  242.         if (cp->bcond != NULL)
  243.             cp->bcond = cblock(cp->bcond);
  244.         if (cp->bfall != NULL)
  245.             cp->bfall = cblock(cp->bfall);
  246.     }
  247.  
  248.     /*
  249.      * Now there are generally blocks that are still linked by the
  250.      * 'chain' pointers, but no longer referenced through 'bcond'
  251.      * or 'bfall' pointers. They don't actually need to be deleted
  252.      * since they won't cause trouble anywhere else.
  253.      */
  254. }
  255.  
  256. /*
  257.  * bwalk() - recursive walk through the branch graph
  258.  *
  259.  * Starting at the entry point, walk through the block graph placing
  260.  * blocks on the output list. By traversing the "bfall" nodes first
  261.  * we attempt to make blocks that fall through come in order so that
  262.  * branches are minimized.
  263.  *
  264.  *
  265.  * The 'lp' variable below maintains our position in the generated list
  266.  * of blocks.
  267.  */
  268. static    BLOCK    *lp;    /* pointer to the next block in the file */
  269.  
  270. #define    TOUCHED(bp)    ((bp)->flags & B_TOUCHED)
  271.  
  272. static    bwalk(p)
  273. register BLOCK    *p;
  274. {
  275.     p->flags |= B_TOUCHED;
  276.     lp->next = p;
  277.     lp = lp->next;
  278.  
  279.     /*
  280.      * We should swap 'bfall' and 'bcond' and alter 'bcode' IF:
  281.      *
  282.      * 1. Both bfall and bcond are non-null.
  283.      * 2. The branch is a simple one (not a DBcc inst.)
  284.      * 3. Branch reversals are enabled.
  285.      * 4. The block at bfall has already been touched.
  286.      * 5. The block at bcond hasn't been touched.
  287.      *
  288.      * In this case, we can avoid an extra branch if we reverse the
  289.      * sense of the conditional branch, and swap the pointers.
  290.      */
  291.     if (p->bfall != NULL && p->bcond != NULL && p->bcode >= 0 &&
  292.         do_brev && TOUCHED(p->bfall) && !TOUCHED(p->bcond)) {
  293.         register BLOCK    *tmp;
  294.  
  295.         s_brev++;
  296.             tmp = p->bfall;
  297.             p->bfall = p->bcond;
  298.             p->bcond = tmp;
  299.             if ((p->bcode = bcomp(p->bcode)) < 0) {
  300.                 fprintf(stderr, "top: internal error in bwalk()\n");
  301.                 exit(EXIT_FAILURE);
  302.             }
  303.     }
  304.  
  305.     if (p->bfall != NULL && !TOUCHED(p->bfall))
  306.         bwalk(p->bfall);
  307.  
  308.     if (p->bcond != NULL && !TOUCHED(p->bcond))
  309.         bwalk(p->bcond);
  310. }
  311.  
  312. /*
  313.  * bsort() - branch optimization
  314.  *
  315.  * Initialize and terminate the 'next' pointers before and after
  316.  * traversing the branch graph.
  317.  */
  318. static    void
  319. bsort(bp)
  320. register BLOCK    *bp;
  321. {
  322.     register BLOCK    *cb;
  323.  
  324.     lp = bp;
  325.  
  326.     bwalk(bp);    /* traverse the tree starting at the entry point */
  327.  
  328.     /*
  329.      * Now look for other parts of the tree that don't appear to be
  330.      * reachable, but really are. This can happen through the jump
  331.      * tables created for switch statements. For each such block,
  332.      * walk the subtree starting with it.
  333.      */
  334.     for (cb = bp; cb != NULL ;cb = cb->chain) {
  335.         if (!TOUCHED(cb) && (cb->flags & B_ISREACHED))
  336.             bwalk(cb);
  337.     }
  338.  
  339.     lp->next = NULL;
  340. }
  341.  
  342. /*
  343.  * bsetlab() - figure out which blocks really need labels
  344.  *
  345.  * This can be called AFTER bsort() to mark the blocks that are going to
  346.  * need labels. Anything that we're going to branch to later gets a label.
  347.  */
  348. static    void
  349. bsetlab(bp)
  350. register BLOCK    *bp;
  351. {
  352.     for (; bp != NULL ;bp = bp->next) {
  353.         if (bp->bcond != NULL)
  354.             cblock(bp->bcond)->flags |= B_LABEL;
  355.         if (bp->bfall != NULL && bp->bfall != bp->next)
  356.             cblock(bp->bfall)->flags |= B_LABEL;
  357.         /*
  358.          * If the block is reached via a jump table, then we
  359.          * need a label on THIS block directly.
  360.          */
  361.         if (bp->flags & B_ISREACHED)
  362.             bp->flags |= B_LABEL;
  363.     }
  364. }
  365.  
  366. /*
  367.  * bjoin() - join blocks that always come together
  368.  *
  369.  * If block 'b' always follows block 'a' unconditionally, then move the
  370.  * instructions in 'b' to the end of 'a', and remove 'b'. This allows us
  371.  * to do better peephole optimization since we can optimize sequences that
  372.  * used to span blocks.
  373.  */
  374. bjoin(bp)
  375. register BLOCK    *bp;
  376. {
  377.     BLOCK    *np, *bnext;
  378.  
  379.     for (; bp != NULL ;bp = bnext) {
  380.         bnext = bp->next;
  381.  
  382.         /*
  383.          * First block can't end with a conditional branch.
  384.          */
  385.         if (bp->bcond != NULL)
  386.             continue;
  387.  
  388.         /*
  389.          * Block must fall through to the next thing in the file.
  390.          */
  391.         if (bp->next == NULL || bp->next != bp->bfall)
  392.             continue;
  393.  
  394.         np = bp->next;
  395.  
  396.         /*
  397.          * Second block can't be the destination of a branch.
  398.          */
  399.         if (np->flags & B_LABEL)
  400.             continue;
  401.  
  402.         /*
  403.          * Join the blocks...
  404.          */
  405.         if (np->first != NULL)
  406.             np->first->prev = bp->last;
  407.  
  408.         if (bp->last != NULL)
  409.             bp->last->next = np->first;
  410.         else {
  411.             bp->first = np->first;
  412.             bp->last = np->last;
  413.         }
  414.  
  415.         if (np->flags & B_RET)
  416.             bp->flags |= B_RET;
  417.  
  418.         bp->last = np->last;
  419.         bp->bfall = np->bfall;
  420.         bp->bcond = np->bcond;
  421.         bp->bcode = np->bcode;
  422.         bp->next = np->next;
  423.  
  424.         /*
  425.          * Fix pointers so we don't free the instructions
  426.          * twice later on.
  427.          */
  428.         np->first = NULL;
  429.         np->last = NULL;
  430.  
  431.         /*
  432.          * If we've done a join, then we want to loop again on
  433.          * the current block to see if any others can be joined.
  434.          */
  435.         bnext = bp;
  436.     }
  437. }
  438.  
  439. /*
  440.  * bopt() - coordinates branch optimization for the given function
  441.  */
  442. void
  443. bopt(bp)
  444. register BLOCK    *bp;
  445. {
  446. #ifdef    DEBUG
  447.     if (debug)
  448.         fprintf(stderr, "bopt() - calling bsplit()\n");
  449. #endif
  450.     bsplit(bp);
  451.  
  452. #ifdef    DEBUG
  453.     if (debug)
  454.         fprintf(stderr, "bopt() - calling bfix()\n");
  455. #endif
  456.     bfix(bp);
  457.  
  458. #ifdef    DEBUG
  459.     if (debug)
  460.         fprintf(stderr, "bopt() - calling bclean()\n");
  461. #endif
  462.     bclean(bp);
  463.  
  464. #ifdef    DEBUG
  465.     if (debug)
  466.         fprintf(stderr, "bopt() - calling bsort()\n");
  467. #endif
  468.     bsort(bp);
  469.  
  470. #ifdef    DEBUG
  471.     if (debug)
  472.         fprintf(stderr, "bopt() - calling bsetlab()\n");
  473. #endif
  474.     bsetlab(bp);
  475.  
  476. #ifdef    DEBUG
  477.     if (debug)
  478.         fprintf(stderr, "bopt() - calling bjoin()\n");
  479. #endif
  480.     bjoin(bp);
  481. }
  482.